//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        if(n == 1)
            return dp[0];
        //dp[i]表示：以i位置元素为结尾的所有子序列中的最长递增子序列的长度
        int retVal = 0;
        for(size_t i = 1 ; i < n ; ++i)
        {
            int maxLen = 0;
            for(size_t j = 0 ; j < i ; ++j)
            {
                if(dp[j] > maxLen && nums[i] > nums[j])
                {
                    maxLen = dp[j];
                    dp[i] = dp[j] + 1;
                }
            }
            if(dp[i] > retVal)
                retVal = dp[i];
        }
        return retVal;
    }
};

//摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n,1);
        //f(x)表示：以x位置元素为结尾的所有子序列中最后一个呈现上升趋势的最长摆动序列的长度
        auto g = f;
        //g(x)表示：以x位置元素为结尾的所有子序列中最后一个呈现下降趋势的最长摆动序列的长度
        int retVal = 1;
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j < i ; ++j)
            {
                if(nums[i]>nums[j])
                {
                    g[i] = max(f[j]+1,g[i]);
                }
                else if(nums[i] < nums[j])
                {
                    //找打了最后一个位置是上升趋势的子序列
                    f[i] = max(g[j]+1,f[i]);
                }
            }
            if(retVal < f[i] || retVal < g[i])
                retVal = max(f[i],g[i]);
        }
        return retVal;
    }
};

